/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-14
 * Time:23:25
 */
import java.util.Scanner;

/**
 * 393. UTF-8 编码验证
 * 给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。
 * UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：
 * 对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。
 * 对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/utf-8-validation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 思路
 * 输入的整数甭管怎么样，都看作8位2进制的数。
 * 从左到右开始模拟，
 * 当前数字如果是0开头的，那么该数字单独成一个1字节字符。
 * 当前数字如果是110开头的，那么该数字需要额外跟着一个10开头的数，构成一个2字节字符。
 * ...
 * 数字开头有xx个1，后面就需要跟着x-1x−1个10开头的数和它划为一组。
 * 每组数字（几个数一组）都由这组数的开头数决定
 **/
public class TestDemo {
    public static boolean validUtf8(int[] data) {
        boolean ans = true;
        int n = data.length;
        //先从前往后出来每个data[i];
        for (int i = 0; i < n; ) {
            int num = data[i];
            int preOneNum = 0;
            int cnt = 0;
            //统计 data[i]data[i] 从第 7 位开始往后有多少位连续的 1，
            // 代表这是一个几字节的字符，记为 preOneNum
            for (int j = 7; j > 0; j--) {
                if (((num >> j) & 1) == 1) {
                    preOneNum++;
                } else {
                    break;
                }
            }
            //如果 preOneNum为 1 或者大于 4 均违反编码规则
            // （与字符长度为 1 时的编码规则 和 字符长度只能是 1 到 4 冲突），
            // 如果字符长度合理;但是整个数组长度小于字符长度也返回 False
            if (preOneNum > 4 || n < preOneNum || preOneNum == 1) {
                ans = false;
                break;
            }
            //否则检查下标范围为 [i + 1, i + preOneNum - 1]的数是否满足
            // 前两位为 10 的要求，若不满足返回 False
            for (int k = i + 1; k <= i + preOneNum - 1; k++) {
                int cur = data[k];
                int flag = 0;
                for (int a = 7; a > 0; a--) {
                    if ((1 & (cur >> a)) == 1) {
                        flag++;
                    } else {
                        break;
                    }
                }
                if (flag == 1) {
                    continue;
                } else {
                    ans = false;
                    break;
                }
            }
            //如果是一个字符长度;则i++
            if (preOneNum == 0) {
                i++;
            } else {
                //否则就跳到下一个检查点
                i += preOneNum;
            }
        }
        return ans;
    }

    public static void main1(String[] args) {
        int[] data = {145};
        System.out.println(validUtf8(data));
    }

    //统计每个月兔子的总数-斐波那契数列
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int month = scanner.nextInt();
        System.out.println(Fibonacci(month));
    }

    private static int Fibonacci(int month) {
        if (month == 1 || month == 2) {
            return 1;
        }
        return Fibonacci(month - 1) + Fibonacci(month - 2);
    }

    //牛客 字符串通配符
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String stringA = scanner.nextLine();
            String stringB = scanner.nextLine();
            stringA = stringA.toLowerCase();
            stringB = stringB.toLowerCase();
            //做相应的替换
            //*{1,} == {m,n}扩展前一个字符m至n次（含n)   *前一个字符0次或无限次扩展
            // [0-9A-Za-z]后面的*代表[0-9A-Za-z]匹配0次或多次
            stringA = stringA.replaceAll("\\*{1,}", "[0-9A-Za-z]*");
            //[0-9a-zA-Z]表示匹配1个数字或1个字母，其中，数字为0到9中的数字，字母为a-z的小写字母或A到Z的大写字母中的一个。
            stringA = stringA.replaceAll("\\?", "[0-9A-Za-z]{1}");
            boolean result = stringB.matches(stringA);
            System.out.println(result);
        }
    }

    //牛客 汽水瓶
    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            //记录总共喝多少瓶汽水
            int count = 0;
            //记录每次换汽水本身剩下多少瓶子
            int bottom = 0;
            while (n / 3 != 0) {
                bottom = 0;
                count += (n / 3);
                bottom += (n % 3);
                //记录每次换取多少瓶牛奶=每次新获取多少瓶子
                n /= 3;
                //喝完一轮后手里一共剩下多少瓶子
                n += bottom;
            }
            //如果剩下的瓶子只有两个;那么还能借一个;喝完再还回去;少于两个则不能换
            if (n == 2) {
                count++;
            }
            System.out.println(count);
        }
    }

    //牛客 查找两个字符串a,b中的最长公共子串
    //穷举法
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s1 = scanner.nextLine();
            String s2 = scanner.nextLine();
            int n = Math.min(s1.length(), s2.length());
            String longer = s1.length() >= s2.length() ? s1 : s2;
            String shorter = s1.length() >= s2.length() ? s2 : s1;
            int max = 0;
            String ans = "";
            for (int i = 0; i < n; i++) {
                for (int j = i; j <= n; j++) {
                    //因为substring(i,j)的范围是前闭后开 所以j 需要 <= n
                    if (longer.contains(shorter.substring(i, j)) && j - i > max) {
                        max = j - i;
                        ans = shorter.substring(i, j);
                    }
                }
            }
            System.out.println(ans);
        }
    }

    //字符串反转
    public static void main7(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.nextLine();
            System.out.println(new StringBuffer(s).reverse());
        }
    }
    //两个字符串a,b中的最长公共子串 字串是连续的 子序列是可以不连续的
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s1 = scanner.nextLine();
            String s2 = scanner.nextLine();
            String longer = s1.length() > s2.length() ? s1 : s2;
            String shorter = s1.length() > s2.length() ? s2 : s1;
            int length = shorter.length();
            int max = 0;
            for (int i = 0; i < length; i++) {
                for (int j = i; j <= length; j++) {
                    if (longer.contains(shorter.substring(i, j)) && j - i > max) {
                        max = j - i;
                    }
                }
            }
            System.out.println(max);
        }
    }
}
